package com.learn.sort;

import cn.hutool.script.ScriptUtil;
import lombok.SneakyThrows;

/**
 * @author zhangjianshan on 2021-05-13
 */
public class QuickSort {
    /**
     * 根据下标交换数组的两个元素
     *
     * @param arr    数组
     * @param index1 下标1
     * @param index2 下标2
     */
    public static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    /**
     * 递归循环实现快排
     *
     * @param arr        数组
     * @param startIndex 快排的开始下标
     * @param endIndex   快排的结束下标
     */
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (arr != null && arr.length > 0) {
            int start = startIndex, end = endIndex;
            //target是本次循环要排序的元素，每次循环都是确定一个元素的排序位置，这个元素都是开始下标对应的元素
            int target = arr[startIndex];
            //开始循环，从两头往中间循环，相遇后循环结束
            while (start < end) {
                //从右向左循环比较，如果比target小，就和target交换位置，让所有比target小的元素到target的左边去
                while (start < end) {
                    if (arr[end] < target) {
                        swap(arr, start, end);
                        break;
                    } else {
                        end--;
                    }
                }

                //从左向右循环比较，如果比target大，就和target交换位置，让所有比target大的元素到target的右边去
                while (start < end) {
                    if (arr[start] > target) {
                        swap(arr, start, end);
                        break;
                    } else {
                        start++;
                    }
                }
            }
            //确定target的排序后，如果target左边还有元素，继续递归排序
            if ((start - 1) > startIndex) {
                quickSort(arr, startIndex, start - 1);
            }
            //确定target的排序后，如果target右边还有元素，继续递归排序
            if ((end + 1) < endIndex) {
                quickSort(arr, end + 1, endIndex);
            }
        }
    }

    @SneakyThrows
    public static void main(String[] args) {
        // 2 1 8 5 3 4 9 10 6 7  end 5
        // 2 1 4 5 3 8 9 10 6 7 start 2

        //4 5 3 8
        //3 5 4 8 end 4
        //3 4 5 8 start 3
        //2 1 3 4 5 8 9 10 6 7
        int[] arr = new int[]{4, 1, 8, 5, 3, 2, 9, 10, 6, 7};
        sort(arr, 0, 9);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
        System.out.println();
        System.out.println(ScriptUtil.getJavaScriptEngine().eval("1+10%3"));
        new ThreadLocal().set(new String());
    }

    public static void quickS(int[] arr, int start, int end) {
        if (arr != null && arr.length > 0) {
            int s = start, e = end;
            int compare = arr[s];
            while (s < e) {
                while (s < e) {
                    if (arr[e] < compare) {
                        swap(arr, s, e);
                        break;
                    } else {
                        e--;
                    }
                }

                while (s < e) {
                    if (arr[s] > compare) {
                        swap(arr, s, e);
                        break;
                    } else {
                        s++;
                    }
                }
            }
            if ((s - 1) > start) {
                quickS(arr, start, s - 1);
            }
            if ((e + 1) < end) {
                quickS(arr, e + 1, end);
            }
        }
    }

    public static void sort(int[] array, int startIndex, int endIndex) {
        int start = startIndex;
        int end = endIndex;
        //取第一个为介质
        int compareInt = array[start];

        while (start < end) {
            //从右向左,把小的放compare左边
            while (start < end) {
                if (compareInt > array[end]) {
                    swap(array, start, end);
                    break;
                } else {
                    end--;
                }
            }

            //从左向右把比compare大的放右边
            while (start < end) {
                if (compareInt < array[start]) {
                    swap(array, start, end);
                    break;
                } else {
                    start++;
                }
            }
        }

        if ((start - 1) > startIndex) {
            sort(array, startIndex, start - 1);
        }
        if ((end + 1) < endIndex) {
            sort(array, end + 1, endIndex);
        }
    }
}
